package one;

import java.util.*;

public class A017 {


    /**
     * 41.缺失的第一个正数
     * @param
     */

    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        //1.让学生坐到他和他学号相同的座位上
        for(int i=0;i<nums.length;i++) {
            //数字在范围[1,n]范围内 && 座位号不想等且本身的值不等于座位号处放的值 （难）
            while(1<=nums[i] && nums[i]<=n && nums[nums[i]-1]!= nums[i] ) {
                swap(nums,i,nums[i]-1);
            }
        }
        //2.第二次遍历
        for(int i=0;i<nums.length;i++) {
            if(nums[i]!=i+1) return i+1;
        }
        return nums.length+1;
    }

    public void swap(int[] nums,int x,int y) {
        int t = nums[x];
        nums[x]=nums[y];
        nums[y]=t;
    }


    public static void main(String[] args) {

    }
}
